//封装链表类
function LinkedList() {
  // 属性
  this.head = null;
  this.length = 0; //记录链表的长度

  // 内部的类: 节点类
  function Node(data) {
    this.data = data;
    this.next = null;
  }

  // 1.追加方法,在末尾追加
  LinkedList.prototype.append = function (data) {
    // 1.创建一个新节点
    let newNode = new Node(data);

    //2.判断是否添加的是第一个节点
    if (this.length == 0) {
      //是第一个节点
      this.head = newNode;
    } else {
      let current = this.head; //当前current保存的是第一个节点
      while (current.next) {
        //这里的判断是不是最后一个节点
        current = current.next; //这里的current保存最后一个节点的next
      }
      current.next = newNode; //是最后一个节点,然后追加节点
    }

    // 最后增加链表长度
    this.length += 1;
  };

  // 2.toString方法
  LinkedList.prototype.toString = function () {
    let current = this.head;
    let listString = ""; //存放字符串的结果
    //2，循环获取一个个的节点.
    while (current) {
      listString += current.data + " ";
      current = current.next;
    }
    return listString;
  };

  //3.insert方法 (根据位置添加元素 (索引))
  LinkedList.prototype.insert = function (position, data) {
    // 判断插入的位置
    if (position < 0 || position > this.length) return false;
    //2，根据data创建newNode
    let newNode = new Node(data);
    // 3，判断插入的位置是否是第一个
    if (position == 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      // 现在position>1
      let index = 0;
      let current = this.head;
      let previous = null;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      newNode.next = current;
      previous.next = newNode;
    }
    // 4.最后的length+1
    this.length += 1;
  };

  //4.get方法,根据位置(索引)返回对应的data
  LinkedList.prototype.get = function (position) {
    //1. 越界判断
    if (position < 0 || position >= this.length) return null;
    // 2，获取对应的data
    let current = this.head;
    let index = 0;
    while (index < position) {
      current = current.next;
      index++;
    }
    return current.data;
  };

  // 5.indexOf方法 (返回索引 位置)
  LinkedList.prototype.indexOf = function (data) {
    //1，定义变量
    let current = this.head;
    let index = 0;

    //2.开始查找
    while (current) {
      if (current.data === data) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  };

  // 6.update方法 (根据索引修改data)
  LinkedList.prototype.update = function (position, newData) {
    // 1.越界判断
    if (position < 0 || position >= this.length) return false;
    // 2，查找正确的节点
    let current = this.head;
    let index = 0;
    while (index++ < position) {
      current = current.next;
    }
    //3.将position位置的node的data修改成newData
    current.data = newData;
    return true;
  };

  //7，removeAt方法 (根据索引,删除data).
  LinkedList.prototype.removeAt = function (position) {
    // 1.越界判断
    if (position < 0 || position >= this.length) return null;

    let current = this.head; //把变量定义放到外面,最后可以返回删除的结果
    let previous = null;

    //2.判断是否删除的是第一个节点
    if (position == 0) {
      this.head = this.head.next;
    } else {
      let index = 0;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      //前一个节点的next指向，current的next即可
      previous.next = current.next;
    }
    // 最后 length -1
    this.length--;
    return current.data;
  };

  //8，remove方法 (根据元素,删除节点).
  LinkedList.prototype.remove = function (data) {
    // 1.获取data在列表中的位置
    let position = this.indexOf(data);
    //  2.根据位置,删除节点
    return this.removeAt(position);
  };

  //9.isEmpty方法
  LinkedList.prototype.isEmpty = function () {
    return this.length == 0;
  };

  //10. size 方法
  LinkedList.prototype.size = function () {
    return this.length;
  };
}

// 测试代码

let list = new LinkedList();
list.append("AA");
list.append("BB");
list.append("CC");
list.insert(1, "DD");

console.log(list.get(1));
console.log(list.indexOf("BB"));
console.log(list.update(0, "MM"));
console.log("删除的元素", list.removeAt(0));
console.log("删除的元素", list.remove("CC"));

console.log(list.toString());
console.log(list);
